//给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。 
//
// 返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度
// 。 
//
// 子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [4,5,2,1], queries = [3,10,21]
//输出：[2,3,4]
//解释：queries 对应的 answer 如下：
//- 子序列 [2,1] 的和小于或等于 3 。可以证明满足题目要求的子序列的最大长度是 2 ，所以 answer[0] = 2 。
//- 子序列 [4,5,1] 的和小于或等于 10 。可以证明满足题目要求的子序列的最大长度是 3 ，所以 answer[1] = 3 。
//- 子序列 [4,5,2,1] 的和小于或等于 21 。可以证明满足题目要求的子序列的最大长度是 4 ，所以 answer[2] = 4 。
// 
//
// 示例 2： 
//
// 
//输入：nums = [2,3,4,5], queries = [1]
//输出：[0]
//解释：空子序列是唯一一个满足元素和小于或等于 1 的子序列，所以 answer[0] = 0 。 
//
// 
//
// 提示： 
//
// 
// n == nums.length 
// m == queries.length 
// 1 <= n, m <= 1000 
// 1 <= nums[i], queries[i] <= 10⁶ 
// 
//
// Related Topics 贪心 数组 二分查找 前缀和 排序 👍 95 👎 0


package leetcode.editor.cn;

// [2389]和有限的最长子序列

import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;

public class LongestSubsequenceWithLimitedSum_2389 {
    public static void main(String[] args) {
        Solution solution = new LongestSubsequenceWithLimitedSum_2389().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] answerQueries(int[] nums, int[] queries) {
            if (nums == null || queries == null) return null;
            int l = 0, r = nums.length - 1;
            mergeSort(nums, l, r);
            int[] prefix = new int[nums.length];
            prefix[0] = nums[0];
            for (int i = 1; i < nums.length; i++) {
                prefix[i] = prefix[i - 1] + nums[i];
            }

            int[] answer = new int[queries.length];
            for (int i = 0; i < queries.length; i++) {
                l = -1;
                r = nums.length;
                int m = l + ((r - l) >> 1);
                while (l != m) {
                    if (prefix[m] <= queries[i]) {
                        l = m;
                        m = m + ((r - m) >> 1);
                    } else {
                        r = m;
                        m = l + ((m - l) >> 1);
                    }
                }
                answer[i] = m + 1;
            }
            return answer;
        }

        public void mergeSort(int[] arr, int l, int r) {
            if (l == r) return;
            int m = l + ((r - l) >> 1);
            mergeSort(arr, l, m);
            mergeSort(arr, m + 1, r);
            merge(arr, l, m, r);
        }

        public void merge(int[] arr, int l, int m, int r) {
            int[] tmp = new int[r - l + 1];
            int p = l, q = m + 1;
            int i = 0;
            while (p <= m && q <= r) {
                tmp[i++] = arr[p] < arr[q] ? arr[p++] : arr[q++];
            }
            while (p <= m) {
                tmp[i++] = arr[p++];
            }
            while (q <= r) {
                tmp[i++] = arr[q++];
            }
            for (int j = 0; j <= (r - l); j++) {
                arr[l + j] = tmp[j];
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}